package com.shixianchen.study.day2;


/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description 现在有一摞纸牌，获取两个两个最大的分数
 * @date 2022/10/30 16:09
 */
public class Code05_CardsInline {


    public static int getWinnerScore2(int[] arr) {
        int n = arr.length+1;
        int [][] dpXian = new int[n][n];
        int [][] dpHou = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dpXian[i][j] = -1;
                dpHou[i][j] = -1;
            }
        }

        int xian = xian2(arr, 0, arr.length-1, dpXian, dpHou);

        int hou =  hou2(arr,0,arr.length-1,dpXian,dpHou);
        return Math.max(xian,hou);
    }

    private static int xian2(int[] arr, int L, int R, int[][] dpXian, int[][] dpHou) {
        //查看缓存是否存在
        if (dpXian[L][R] != -1){
            return dpXian[L][R];
        }

        int ans = 0;

        //当只剩一张纸牌
        if (L == R){
            ans = 0;
        }else if (L == R-1){
            //当存在两张牌的获取最大的
            ans = Math.max(arr[L],arr[R]);
        }else {
            //当L..R上不止两张牌的时候
            //可能性1：获取L位置上的牌
            int p1 = arr[L] + hou2(arr,L+1,R,dpXian,dpHou);
            //可能性2：获取R位置上的牌
            int p2 = arr[R] + hou2(arr,L,R-1,dpXian,dpHou);
            //获取最大的值
            ans = Math.max(p1,p2);
        }
        //放入缓存
        dpXian[L][R] = ans;
        return ans;
    }



    private static int hou2(int[] arr, int L, int R, int[][] dpXian, int[][] dpHou) {
        //查看缓存是否存在
        if (dpHou[R][L] != -1){
            return dpHou[R][L];
        }

        int ans = 0;
        //只剩一张牌
        if (L == R){
            ans = 0;
        }else if (L == R -1){
            //省两张牌
            //后手函数
            ans = Math.min(arr[L],arr[R]);
        }else {
            //当牌大于两个的情况
            //先先手，选完，后手选择L 位置的牌
            int p1 =  xian2(arr,L+1,R,dpXian,dpHou);
            //先手，选完，后手选择R 位置的牌
            int p2 = xian2(arr,L,R-1,dpXian,dpHou);
            //先手选择完成，后手没有选择的余地，这里面指的是绝对聪明的
            ans = Math.min(p1,p2);
        }
        //放入缓存
        dpHou[L][R] = ans;

        return ans;
    }


    /**
     * 获取获胜的分数
     * @param arr 分数数组
     * @return 最大分数
     */
    public static int getWinnerScore1(int[] arr) {
        int xian = xian1(arr, 0, arr.length - 1);
        int hou = hou1(arr, 0, arr.length - 1);
        return Math.max(xian, hou);
    }

    //目前,是在arr[L...R]这个给范上玩牌的
    //返回 ,先手最终的最大的得分

    public static int xian1(int[] arr, int L, int R) {
        //一张牌的情况
        if (L == R) {
            return arr[L];
        }

        if (L == R - 1) {
            return Math.max(arr[L], arr[R]);
        }

        // L...R,不止两张牌
        //可能性1：拿走L位置的牌
        int p1 = arr[L] + hou1(arr, L + 1, R);
        //可能性2：拿走R位置的牌
        int p2 = arr[R] +  hou1(arr, L, R - 1);

        return Math.max(p1, p2);

    }
    //目前,是在arr[L...R]这个给范上玩牌的
    //返回 ,后手最终的最大的得分

    private static int hou1(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }

        if (L == R - 1) {
            return Math.min(arr[L], arr[R]);
        }

        // L...R,不止两张牌
        //可能性1：对手，先手，拿走L位置上的牌，接下来！，你就可以在L+1..R上先手了！
        int p1 = xian1(arr, L + 1, R);

        //可能性2：对手，先手，拿走R位置上的牌，接下来，你就可以在L，R-1上先手了!
        int p2 =  xian1(arr, L, R - 1);

        return Math.min(p1, p2);
    }


    public static void main(String[] args) {
        int[] arr = new int[]{2,3,48,7,99,1,3,77};
        System.out.println("getWinnerScore1(arr) = " + getWinnerScore1(arr));
        System.out.println("getWinnerScore2(arr) = " + getWinnerScore2(arr));

    }

}
